/**
 * [84] 柱状图中最大的矩形
 * 思路：
 *
 * @format
 * @lc app=leetcode.cn id=84 lang=javascript
 */

// @lc code=start
/**
 * @param {number[]} heights
 * @return {number}
 */
// 栈
var largestRectangleArea = function (heights) {
    const stack = [-1]
    let [max, temp, p] = [0, 0, 0]
    for (let i = 0; i <= heights.length; i++) {
        while (true) {
            // 入栈：栈空 or 当前柱子不低于栈顶柱子
            if (p == 0 || heights[i] >= heights[stack[p]]) {
                stack.push(i)
                p++
            }
            // 出栈：遍历结束 or 当前柱子低于栈顶柱子
            else if (i == heights.length || heights[i] < heights[stack[p]]) {
                // 计算栈顶柱框面积：高*宽
                temp = heights[stack[p]] * (i - stack[p - 1] - 1)
                if (temp > max) max = temp
                stack.pop()
                p--
            }
            // 结束本轮栈操作：出栈至栈空 or 入栈至当前柱子
            if (stack[p] == i || (p == 0 && i == heights.length)) break
        }
    }
    return max
}
debugger
const heights = [0, 0]
const AREA = largestRectangleArea(heights)
console.log(AREA)
// 暴力算法
// var largestRectangleArea = function (heights) {
//     let max = 0
//     for (let i = 0; i < heights.length; i++) {
//         let [left, right] = [i, i]
//         let [flagL, flagR] = [true, true]
//         while (flagL || flagR) {
//             flagL = heights[left - 1] >= heights[i]
//             flagR = heights[right + 1] >= heights[i]
//             if (flagL) left--
//             if (flagR) right++
//         }
//         let area = heights[i] * (right - left + 1)
//         if (area > max) max = area
//     }
//     return max
// }
// 提交结果：
// Time Limit Exceeded
// 87/98 cases passed (N/A)
// @lc code=end
